package com.markus.code.exam.小米;

import java.util.Stack;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/7 10:10
 * todo:
 */
public class PchDemo {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public boolean process(TreeNode root){
        if (root == null){
            return true;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        TreeNode l = root.left;
        TreeNode r = root.right;
        while(l!=null || r != null || !stack1.isEmpty() || !stack2.isEmpty()){
            while(l != null && r != null){
                stack1.push(l);
                l = l.left;
                stack2.push(r);
                r = r.right;
            }
            if (l != null || r != null){
                return false;
            }
            l = stack1.pop();
            r = stack2.pop();
            if (l.val != r.val){
                return false;
            }
            l = l.right;
            r = r.left;
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        PchDemo demo = new PchDemo();
        System.out.println(demo.process(root));
    }
}
